package com.mlh.stack;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author 缪林辉
 * @date 2024/6/28 14:54
 * @DESCRIPTION
 */
// 给定一个经过编码的字符串，返回它解码后的字符串。
// 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
// 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
// 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
// 示例 1：
// 输入：s = "3[a]2[bc]"
// 输出："aaabcbc"
// 示例 2：
// 输入：s = "3[a2[c]]"
// 输出："accaccacc"
public class 字符串解码 {
    //本题难点在于括号内嵌套括号，需要从内向外生成与拼接字符串，这与栈的先入后出特性对应。
    //算法流程：(力扣)
    // 构建辅助栈 stack， 遍历字符串 s 中每个字符 c；
    // 当 c 为数字时，将数字字符转化为数字 num，用于后续倍数计算；
    // 当 c 为字母时，在 partRes 尾部添加 c；
    // 当 c 为 [ 时，将当前 num 和 partRes 分别入栈，并分别置空置 0：
    // 记录此 [ 前的临时结果 partRes 至parts栈，用于发现对应 ] 后的拼接操作；
    // 记录此 [ 前的倍数 num 至nums栈，用于发现对应 ] 后，获取 repeatNum × [...] 字符串。
    // 进入到新 [ 后，partRes 和 nums 重新记录。

    // 当 c 为 ] 时，parts 出栈，nums出栈，然后拼接字符串 partRes = last_res(parts出栈字符串) + num * partRes，注意：partsRest不入栈
    // 其中:
    // last_res是上个 [ 到当前 [ 的字符串，例如 "3[a2[c]]" 中的 a；
    // num是当前 [ 到 ] 内字符串的重复倍数，例如 "3[a2[c]]" 中的 2。
    // 返回字符串 res。
    public String method1(String s) {
        int num=0;
        LinkedList<Integer>nums=new LinkedList<>();//数字栈
        LinkedList<String>parts=new LinkedList<>();//字符串栈
        StringBuilder partRes=new StringBuilder();//用于记录字符串，最终记录了结果字符串
        for (char c:s.toCharArray()){
            if(c>='0'&&c<='9'){//如果是数字
                num=num*10+(c-'0');
            }else if(c=='['){//如果是[
                nums.add(num);
                parts.add(partRes.toString());
                num=0;
                partRes=new StringBuilder();
            } else if (c==']') {//如果是]
                int repeatNum=nums.removeLast();//弹出重复倍数
                StringBuilder cur=new StringBuilder();//临时partRes的重复结果
                for (int i = 1; i <=repeatNum ; i++) {
                    cur.append(partRes);
                }
                if(parts.size()!=0){//看看parts栈中有没有元素
                    partRes=new StringBuilder(parts.removeLast()+cur);//有的话弹出一个字符串拼接上临时结果形成新的partRes（由内向外的过程）
                }else{
                    partRes=new StringBuilder(cur);
                }
            }else{//如果是字符
                partRes.append(c);
            }
        }
        return partRes.toString();
    }

    public String practice(String s) {
        LinkedList<StringBuilder>parts=new LinkedList<>();
        LinkedList<Integer>nums=new LinkedList<>();
        StringBuilder part=new StringBuilder();
        int num=0;
        for (char c:s.toCharArray()){
            if(c-'0'<=9&&c-'0'>=0){//判断是否是是数字
                num=num*10+(c-'0');
            }else if(c=='['){//判断是否是[
                nums.push(num);
                num=0;
                parts.push(part);
                part=new StringBuilder();
            }else if(c==']'){//判断是否是]
                String tempPart=part.toString();
                int tempNum=nums.pop();
                for (int i = 0; i < tempNum-1; i++) {//注意这里为啥是tempNum-1  因为你原本part字符已经相当于1次了
                    part.append(tempPart);
                }
                StringBuilder pop = parts.pop();
                part=pop.append(part);
            }else{//判断是否是字母
                part.append(c);
            }
        }
        return part.toString();
    }

    public String practice2(String s) {
        LinkedList<Integer>numStack=new LinkedList<>();
        LinkedList<String>strStack=new LinkedList<>();
        char[] chars = s.toCharArray();
        int num=0;
        StringBuilder partStr=new StringBuilder();
        for (int i = 0; i < chars.length; i++) {
            if(chars[i]-'0'<=9&&chars[i]-'0'>=0){
                num*=10;
                num+=(chars[i]-'0');
            }else if(chars[i]=='['){
                numStack.push(num);
                num=0;
                strStack.push(partStr.toString());
                partStr.delete(0,partStr.length());
            }else if(chars[i]==']'){
                StringBuilder pop = new StringBuilder(strStack.pop());
                String temp=partStr.toString();
                int count=numStack.pop();
                for (int j = 0; j < count; j++) {
                    pop.append(temp);
                }
                partStr=pop;
            }else{
                partStr.append(chars[i]);
            }
        }
        return partStr.toString();
    }

    public static void main(String[] args) {
        LinkedList<String>parts=new LinkedList<>();
        parts.add("a");
        System.out.println(parts.pollLast());
        System.out.println(parts.pollLast());//返回null
        System.out.println("-------------------");
        System.out.println(parts.removeLast());//抛出NoSuchElementException
    }
}
